本场链接:Codeforces Round #623
A. Dead Pixel
题目大意:有一个大小的电视机,坐标从开始.上面有一个像素点坏了,问不包括这个坏掉的像素点的矩形最大的面积是多少.
数据范围:
这题还是比较显然的,去掉这个坏掉的像素点之后,最大的矩形就四种情况,分别求一个最大值就行了.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m,x,y;scanf("%d%d%d%d",&n,&m,&x,&y);
int res = 0;
res = max(res,max(n * y,n * (m - y - 1)));
res = max(res,max(m * x,m * (n - x - 1)));
printf("%d\n",res);
}
return 0;
}
B. Homecoming
原题大意:一个人一开始在号位置,一条路上一共有个车站,用一个字符串来表示整条路上的车站分布情况.车站一共有两种,一种是A,花费为,另外一种是B,花费为.车站的行驶规则是这样的:假如有一段全是A或全是B,那么就可以从这段起点一直走到这一段的末尾的下一个位置(下一个位置可以是不同的),并支付相应的花费.现在已知和两种票价以及整条路径上的路线安排情况,以及手上有多少钱.问至少要走几步,才能使之后一直到位置都可以只坐车到达.要求不能欠钱,也不必把钱花完.最终输出至少有几步即可.
数据范围:
这题的题面有点长,不过理解了之后思路还是比较明确的,只要从后往前模拟就可以了.注意模拟的退出点是:手上钱不够购买一段连续区间的车票钱,或者是已经到头了.以及要记录一个当前这一段相同区间的左端点的答案,如果退出循环之后,手上的钱是足够购买这一段区间的票钱的,那么说明应该选择这一段的右端点,如果不够,应该选这一段的左端点.细节问题稍微有点说不清楚,建议自行模拟一下这个题的过程.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
char s[N];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
while(T--)
{
int a,b,p;cin >> a >> b >> p;
cin >> s + 1;
int n = strlen(s + 1);
int r = n - 1;
int l = r,res = 0;
while(l >= 0)
{
while(l >= 0 && s[l] == s[r]) --l;
res = l + 1;
if(l == 0) break;
if(s[r] == 'A')
{
if(p >= a) p -= a;
else break;
}
else if(s[r] == 'B')
{
if(p >= b) p -= b;
else break;
}
r = l;
}
if(p < ((s[r] == 'A') ? a : b)) cout << r + 1 << endl;
else cout << res << endl;
}
return 0;
}
C. Restoring Permutation
题目大意:给定一个长度为的序列,找到一个字典序最小的排列,长度为,并满足,若不存在这样的排列,则输出,否则输出
注意是一个排列,不是单纯的序列
数据范围:
这题的数据范围一看这么小,肯定可以乱搞搞就过去了.
思考一下这个题具体是在问什么:找到一个排列,要使这个排列满足一个性质,如果有多个,就得是最小的.
显然,对于一个数字排列来说,只要数字越小字典序也就越小,首先肯定是能选小的就选小的.其次很容易想到这个题应该是一步一步,从后往前依次把里的元素放进去,再按的大小构造的,每次要往里造两个元素放进去,每两个都要满足之前的性质.不难想到说放完了一个里的元素之后,插入一个还没有用过的比当前元素要大的数接着放进去.因为要取最小值,,如果后一个里的元素被影响了(后面的这个数更大,导致之前插入给之前那个元素补更大的值在这里变成了一个较小值),说明无解.因为如果一个更大的数放在这里,这个较小的数之后不管怎样放,必然会产生矛盾,而且作为一个排列不能是缺少一些数的,所以无解.
要用没有用过的数的原因是最后的得是一个排列.最后如果还有没有用完的数,就把剩余的还没加进的数从小到大依次放进去就好了.
至于这个查找的过程,可以直接循环遍历一下,最多也就个数,随便写写就完事了.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
set<int> st;
int n;scanf("%d",&n);
vector<int> b(n + 17,0);
if(n == 1)
{
scanf("%d",&b[0]);
if(b[0] != 1) puts("-1");
else puts("1 2");
continue;
}
for(int i = 1;i <= n;++i) scanf("%d",&b[i]);
for(int i = 1;i <= 2 * n;++i) st.insert(i);
for(int i = 1;i <= n;++i) st.erase(b[i]);
vector<int> a;a.push_back(0x3f3f3f3f);
a.push_back(b[1]);
for(int i = b[1];i <= 2 * n;++i)
if(st.count(i))
{
a.push_back(i);
st.erase(i);
break;
}
for(int i = 2;i <= n;++i)
{
a.push_back(b[i]);
for(int j = b[i] + 1;j <= 2 * n;++j)
if(st.count(j))
{
st.erase(j);
a.push_back(j);
break;
}
}
for(int i = 1;i <= 2 * n;++i)
{
if(st.count(i))
a.push_back(i);
}
//check
int ok = 1;
// for(auto& v : a) cout << v << " ";cout << endl;
for(int i = 1;i <= n;++i)
{
if(b[i] != min(a[2 * i],a[2 * i - 1]))
{
ok = 0;
break;
}
}
if(!ok) puts("-1");
else
{
for(int i = 1;i <= 2 * n;++i)
printf("%d ",a[i]);
puts("");
}
}
return 0;
}
D. Recommendations
题目大意:有个元素,每个元素有两种属性,一是,另外一个是,表示如果要让加一,需要的代价.现要使所有的都不同,问最少需要多少代价.
数据范围:
爆
这个题的关键在于,a_是动态变化的,如果我把一个加一,那么其他的的数量可能因此增加.这是一个动态的数量变化,与动态的变化的结构有很多,在这里比较容易依靠直觉想到的是堆或者用并查集维护.两种方法都可以做,这里讲一下并查集怎么做.
首先要知道并查集到底在维护什么,我们可以发现,如果对于某一个值来说,他增加了一次,那么之后所有其他值就不能采用他这个值了,就应该是这个值.所以可以维护每一个值最终需要是多少.对于第一个遇到的,就是,之后把的祖先连接到.动态的维护最终要是多少即可.
简略说一下整个算法流程:首先贪心的按倒序排列,因为较早出来的值其修改的次数也越少,这样可以贪心的使整个代价较小.其次遍历每一个元素,查他的祖先,即最终需要是多少,计算一个差值,求出这个差值和的乘积,得到应该需要增加几次,以及要多少的代价,并累加到答案里.
最后还有一个问题,因为的值高达,因此这里可以采用来做并查集,可以避免值域的问题(也就是避免写离散化,而且离散化貌似也不能处理增加的处理).
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e5+7;
map<int,int> fa;
struct Node
{
int a,b;
const bool operator<(const Node& v) const
{
if(b != v.b) return b > v.b;
return a < v.a;
}
}a[N];
int find(int x)
{
if(fa[x] == 0) return x;
return fa[x] = find(fa[x]);
}
signed main()
{
int n;scanf("%lld",&n);
for(int i = 1;i <= n;++i) scanf("%lld",&a[i].a);
for(int i = 1;i <= n;++i) scanf("%lld",&a[i].b);
sort(a + 1,a + n + 1);
ll res = 0;
for(int i = 1;i <= n;++i)
{
int x = find(a[i].a);
res += (x - a[i].a) * a[i].b;
int nxt = find(x + 1);
fa[x] = nxt;
}
printf("%lld",res);
return 0;
}